﻿#ifndef TREE_H
#define TREE_H
/**
  *@brief 基本的二叉树，此创建二叉树要按照前序(或中序后序)按顺序输入二叉树
*/
#include <iostream>
#include <stack>
#include <queue>
using namespace std;

/**
  *@brief 树的链式存储结构，表示树的一个结点，一个数据域，两个指针域
*/
template <typename T>
struct BinaryTreeNode
{
	T  element;
    BinaryTreeNode<T> *lchild;
    BinaryTreeNode<T> *rchild;

    void print()
    {
        cout<<element<< ";";
    }
};
/**
  *@brief 非递归后序遍历结构
*/
template <typename T>
struct BinaryTreeNodePost
{
    BinaryTreeNode<T> * biTree;
	char tag;
};

template<typename T>
class BinaryTree
{
public:
     BinaryTree()  { root = NULL; Treesize = 0; }
    ~BinaryTree() { erase(root); }

    void erase(BinaryTreeNode<T> * &node);

	bool empty() const{ return Treesize == 0; }
	int  size() const{ return Treesize; }


	//递归遍历方法
    void preOrder(BinaryTreeNode <T>* &node);
    void inOrder(BinaryTreeNode <T>* &node);
    void postOrder(BinaryTreeNode <T>* &node);

    //非递归遍历方法
    void preOrderStack(BinaryTreeNode<T>* node);
    void inOrderStack(BinaryTreeNode <T>* node);
    void postOrderStack(BinaryTreeNode<T>* node);
    void levelOrderQueue(BinaryTreeNode<T>* node);
    void PostOrderTraversalStack(BinaryTreeNode<T>* node);

	//深度
    int Treedepth(BinaryTreeNode <T>*node) const;
    //访问根结点,此处返回的为引用，当不是引用是返回的是root的复制品，也就是一个临时变量，并不能改变root本身。
    BinaryTreeNode<T> * & Root(){ return root; }
protected:
    BinaryTreeNode <T>* root;
	int Treesize;
};

/**
  *@brief 递归方法删除node所指的二叉树
*/
template<typename T>
void BinaryTree<T>::erase(BinaryTreeNode <T>* &node)
{
    if(node != NULL)
	{
		erase(node->lchild);
		erase(node->rchild);
		delete node;
		Treesize--;
		node = NULL;
	}

}

/**
  *@brief 递归前序，中序，后序遍历
*/
template<typename T>
void BinaryTree<T>::preOrder(BinaryTreeNode <T>* &node)
{
	if (node != NULL)
	{
        node->print();
		preOrder(node->lchild);
		preOrder(node->rchild);
	}
}
template<typename T>
void BinaryTree<T>::inOrder(BinaryTreeNode<T>* &node)
{
	if (node != NULL)
	{
		inOrder(node->lchild);
        node->print();
		inOrder(node->rchild);
	}
}
template<typename T>
void BinaryTree<T>::postOrder(BinaryTreeNode <T>* &node)
{
	if (node != NULL)
	{
		postOrder(node->lchild);
		postOrder(node->rchild);
        node->print();
	}
}

/**
  *@brief 非递归层序，前序，中序，后序遍历
*/
template<typename T>
void BinaryTree<T>::preOrderStack(BinaryTreeNode<T>* node)
{
    stack<BinaryTreeNode<T> *> s;
    BinaryTreeNode<T> * p = node;     //p是遍历指针
    while (p || !s.empty())           //p不为空或者栈不空时循环
	{
		if (p != NULL)
		{
			s.push(p);
            p->print();
			p = p->lchild;
		}
		else
		{
			p = s.top();
			s.pop();
			p = p->rchild;
		}
	}

}
template<typename T>
void BinaryTree<T>::inOrderStack(BinaryTreeNode<T> * node)
{
    stack<BinaryTreeNode<T> *> s;
    BinaryTreeNode<T> * p = node;
	while (p || !s.empty())
	{
		if (p != NULL)
		{
			s.push(p);
			p = p->lchild;
		}
		else
		{
			p = s.top();
            p->print();
			s.pop();
			p = p->rchild;
		}
	}
}
template<typename T>
void BinaryTree<T>::postOrderStack(BinaryTreeNode<T> * node)
{
    stack<BinaryTreeNodePost <T>*> s;
    BinaryTreeNode<T> * p = node;
    BinaryTreeNodePost<T> *BT;
	while (p != NULL || !s.empty())
	{
		//遍历左子树
		while (p != NULL)
		{
            BT = new BinaryTreeNodePost<T>;
			BT->biTree = p;
			BT->tag = 'L';
			s.push(BT);
			p = p->lchild;
		}
		//左右子树访问完毕访问根节点
		while (!s.empty() && (s.top())->tag == 'R')
		{
			BT = s.top();
            BT->biTree->print();
			s.pop();
		}
		//遍历右子树
		if (!s.empty())
		{
			BT = s.top();
			BT->tag = 'R';
			p = BT->biTree;
			p = p->rchild;
		}
	}
}
template<typename T>
void BinaryTree<T>::levelOrderQueue(BinaryTreeNode<T> * node)
{
    queue<BinaryTreeNode <T>*> q; //此处为队列
    BinaryTreeNode<T> * p = node;
	q.push(p);                    //队列不空循环
	while (!q.empty())
	{
		p = q.front();
        p->print();
		q.pop();
		if (p->lchild != NULL)
			q.push(p->lchild);
		if (p->rchild != NULL)
			q.push(p->rchild);
    }
}
/**
  * @brief 后序遍历，采用stack方式，以空间换时间，用2个stack，所有节点全部压栈
*/
template<typename T>
void BinaryTree<T>::PostOrderTraversalStack(BinaryTreeNode<T> *node)
{
    if(!node){
        return;
    }
    BinaryTreeNode<T> *p = node;

    stack<BinaryTreeNode<T>*> S;
    stack<BinaryTreeNode<T>*> postOrder;
    S.push(p);
    while(!S.empty()){
        p = S.top();
        postOrder.push(p);
        S.pop();
        if(p->lchild){
            S.push(p->lchild);//first IN, later OUT
        }
        if(p->rchild){
            S.push(p->rchild);//later IN, first OUT
        }
    }
    while(!postOrder.empty()){
        p = postOrder.top();
        if(nullptr == p)
        {
            postOrder.pop();
            continue;
        }
        p->print();
        postOrder.pop();
    }
}

/**
  *@brief 递归方法返回树的深度
*/
template<typename T>
int BinaryTree<T>::Treedepth(BinaryTreeNode<T> *node) const
{
    int hl, hr;
    if (node == NULL)
    {
        return 0;
    }
    hl = Treedepth(node->lchild);
    hr = Treedepth(node->rchild);
    return hl>hr ? ++hl : ++hr;
}

#endif // TREE_H
